\documentclass[10pt]{article}
\usepackage{amsmath}
\usepackage{graphicx}
\setlength{\parskip}{1ex plus 0.3ex minus 0.2ex}

\newcommand{\problem}[1]{\noindent{\sc Problem #1.}}
\newcommand{\solution}{\noindent{\sc Solution.}}
\newcommand{\answer}{\noindent{\sc Answer. }}

\begin{document}

\problem{151}
Paper sheets of standard sizes: an expected-value problem.

A printing shop runs 16 batches (jobs) every week and each batch requires a sheet of special color-proofing paper of size A5.

Every Monday morning, the foreman opens a new envelope, containing a large sheet of the special paper with size A1.

He proceeds to cut it in half, thus getting two sheets of size A2. Then he cuts one of them in half to get two sheets of size A3 and so on until he obtains the A5-size sheet needed for the first batch of the week.

All the unused sheets are placed back in the envelope.
\begin{center}
\includegraphics[height=40mm]{p151.png}
\end{center}

At the beginning of each subsequent batch, he takes from the envelope one sheet of paper at random. If it is of size A5, he uses it. If it is larger, he repeats the 'cut-in-half' procedure until he has what he needs and any remaining sheets are always placed back in the envelope.

Excluding the first and last batch of the week, find the expected number of times (during each week) that the foreman finds a single sheet of paper in the envelope.

Give your answer rounded to six decimal places.

\solution

We use a recursive formula to solve the problem. Denote $N(a_2,a_3,a_4,a_5)$ as the number of expected times the foreman finds a single piece of paper in the envelope, excluding the last batch where there is only one piece of A5 paper, starting with a paper configurations of $a_2$ pieces of A2 paper, $a_3$ pieces of A3 paper, $a_3$ pieces of A3 paper, $a_4$ pieces of A4 paper.

Let $p = a_2+a_3+a_4+a_5$ be the total number of pieces. Then it's easy to find the following recursive formula:
\begin{align}
N(a_2, a_3, a_4, a_5) &= \frac{a_2}{p} \times N(a_2-1, a_3+1, a_4+1, a_5+1) \notag \\
&+ \frac{a_3}{p} \times N(a_2, a_3-1, a_4+1, a_5+1) \notag \\
&+ \frac{a_4}{p} \times N(a_2, a_3, a_4-1, a_5+1) \notag \\
&+ \frac{a_5}{p} \times N(a_2, a_3, a_4, a_5-1) \notag \\
&+ I(p = 1) \notag
\end{align}
with boundary condition $N(\cdot)=0$ if $p=a_5$.

\answer
$N(1,1,1,1) = 0.464399$.

\end{document} 